//
// Created by 黄扬航 on 2023/4/5.
//
#pragma once

#include <vector>
#include <queue>
#include <iostream>
#include <limits>
#include "ErrorCodeDefine.h"

using namespace std;

struct DirectGraphItem
{
    int w, n; //w为权重，n为下个节点
    DirectGraphItem(int _w, int _n) : w(_w), n(_n) {};

    bool operator<(const DirectGraphItem& q) const
    {
        return w > q.w;
    }
};

class DynamicDirectGraph
{
public:
    using DirectGraphItemList = std::vector<DirectGraphItem>; //别名
    DynamicDirectGraph() = delete;  //删除构造函数
    DynamicDirectGraph(uint32_t size) : Size(size)
    {
        Dis = std::vector<uint32_t>(2 * size + 10, std::numeric_limits<uint32_t>::max());
        Check = std::vector<bool>(size + 10,false);
        ItemTable = std::vector<DirectGraphItemList>(size + 10);
        Vis= new bool[size];
    }
    ~DynamicDirectGraph() = default; //析构函数
    ECOperateResult Insert(int start, int go, int w);

    ECOperateResult Dijkstra(int start);

    void DFS(int Node,int flag=0);
protected:
    uint32_t Size;
    bool* Vis;
    std::vector<uint32_t> Dis{};
    std::vector<bool> Check{};
    std::vector<DirectGraphItemList> ItemTable;
    std::priority_queue<DirectGraphItem> DoDijkstra;
};

struct UnDirectGraphItem
{
    int w, n; //w为权重，n为下个节点
    UnDirectGraphItem(int _w, int _n) : w(_w), n(_n) {};

    bool operator<(const UnDirectGraphItem& q) const
    {
        return w > q.w;
    }
};

class DynamicUnDirectGraph
{
public:
    using UnDirectGraphItemList = std::vector<UnDirectGraphItem>; //别名
    DynamicUnDirectGraph() = delete;  //删除构造函数
    DynamicUnDirectGraph(uint32_t size) :
            Size(size),
            Dis(2 * size + 10, std::numeric_limits<uint32_t>::max()),
            Check(size + 10, false),
            Item(2 * size + 10, UnDirectGraphItemList{})
    {
    }

    ~DynamicUnDirectGraph() = default; //析构函数
    ECOperateResult Insert(int start, int go, int w);

    ECOperateResult Prim();

    uint32_t Ans = 0;
protected:
    uint32_t Size;
    std::vector<uint32_t> Dis{};
    std::vector<bool> Check{};
    std::vector<UnDirectGraphItemList> Item;
    std::priority_queue<DirectGraphItem, std::vector<DirectGraphItem> > DoPrim;
};